题目:
算术表达式有前缀表示法、中缀表示法和后缀表示法等形式。日常使用的算术表达式是采用中缀表示法,即二元运算符位于两个运算数中间。请设计程序将中缀表达式转换为后缀表达式。
输入格式:
输入在一行中给出不含空格的中缀表达式,可包含+、-、*、\以及左右括号(),表达式不超过20个字符。
输出格式:
在一行中输出转换后的后缀表达式,要求不同对象(运算数、运算符号)之间以空格分隔,但结尾不得有多余空格。
输入样例:
输出样例:
思路
将中缀表达式转化为后缀表达式的方法就是从头到尾去遍历中缀表达式,利用栈来存运算符,看到数字相关的字符就输出,当遇到运算符(包括括号)时,我们要去判断该运算符与栈顶运算符优先级谁大谁小,若栈顶的大,那么栈顶的运算符可以被输出,但要是该运算符的优先级更大,我们便不能着急的输,因为我们还不知道后面有没有比它更高优先级的运算符,只能将其压入堆栈。
需要注意碰到括号的情况,当碰到的是左括号,我们是将其当作高优先级的运算符直接压入栈中,而碰到右括号时,我们应将栈顶的运算符输出,知道栈顶为左括号(括号里先算)或者栈空为止。
对于这道题还有一个更恶心的点,那就是数字可能为小数或者负数,所有我们再处理数字的时候也应将小数点和负号当作运算数来考虑,但由于本题不要求求出结果,所以我们只需原样入栈出栈输出即可。
代码如下:
代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56
| #include <bits/stdc++.h>
using namespace std;
int main() { string str; cin>>str; stack<char> s; map<char,int> m; m['+']=m['-']=1;m['*']=m['/']=2; int flag=1; for(int i=0;i<str.length();i++) { if((i<1||!isdigit(str[i-1])&&str[i-1]=='(')&&(str[i]=='+'||str[i]=='-')||isdigit(str[i])) { if(flag) flag=0; else putchar(' '); if(str[i]!='+') cout<<str[i]; while(str[i+1]=='.'||isdigit(str[i+1])) { cout<<str[++i]; } } else { if(str[i]=='(') s.push(str[i]); else if(str[i]==')') { while(!s.empty()&&s.top()!='(') { printf(" %c",s.top()); s.pop(); } s.pop(); } else { while(!s.empty()&&s.top()!='('&&m[s.top()]>=m[str[i]]) { printf(" %c",s.top()); s.pop(); } s.push(str[i]); } } } while(!s.empty()) { printf(" %c",s.top()); s.pop(); } }
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70
| #include <bits/stdc++.h>
using namespace std;
int main() { string str; cin>>str; stack<char> s; int flag=0; for(int i=0; i<str.length(); i++) { if((str[i]=='+'||str[i]=='-')&&(!i||str[i-1]=='(')||isdigit(str[i])) { if(flag) putchar(' '); if(str[i]!='+') { cout<<str[i]; flag=1; } while(str[i+1]=='.'||isdigit(str[i+1])) { cout<<str[++i]; flag=1; } } else { if(str[i]==')') { while(!s.empty()&&s.top()!='(') { if(flag) putchar(' '); cout<<s.top(); flag=1; s.pop(); } if(!s.empty()) s.pop(); } else { if(s.empty()) { s.push(str[i]); continue; } while(!s.empty()&&s.top()!='(') { if(str[i]=='('||((str[i]=='*')||str[i]=='/')&&(s.top()=='+'||s.top()=='-')) { break; } if(flag) putchar(' '); cout<<s.top(); flag=1; s.pop(); } s.push(str[i]); } } } while(!s.empty()) { if(flag) putchar(' '); cout<<s.top(); flag=1; s.pop(); } }
|